Thứ tự các giao dịch có giới hạn không công bằng: Định nghĩa, độ phức tạp và cấu trúc
Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions.
Một cân nhắc quan trọng trong bối cảnh của các giao thức sổ cái phân tán là tính công bằng về thứ tự giao dịch. Công việc gần đây [Crypto 2020] đã tiết lộ mối liên hệ giữa sự công bằng trong thứ tự (người nhận) với lý thuyết lựa chọn xã hội và các kết quả bất khả thi liên quan phát sinh từ nghịch lý Condorcet. Do không thể thực hiện được nên nhiều biện pháp nới lỏng thứ tự công bằng đã được đề xuất trong các công việc trước đó. Do các giao thức sổ cái phân tán, đặc biệt là các giao thức xử lý hợp đồng thông minh, phải tuần tự hóa các giao dịch đầu vào, mục tiêu tự nhiên là giảm thiểu khoảng cách (về số lượng giao dịch) giữa bất kỳ cặp giao dịch nào được sắp xếp không công bằng trong sổ cái đầu ra - một khái niệm mà các tác giả gọi là giới hạn không công bằng. Theo cách nói của sao chép máy trạng thái (SMR), điều này yêu cầu giảm thiểu số lượng cập nhật trạng thái không công bằng xảy ra trước khi xử lý bất kỳ yêu cầu nào. Mục tiêu giảm thiểu sự không công bằng này làm nảy sinh một lớp định nghĩa tự nhiên về tham số thứ tự công bằng chưa được nghiên cứu trước đây. Các tác giả nhận thấy, những nới lỏng có thể thực hiện được trước đây về thứ tự công bằng không mang lại những giới hạn không công bằng tốt. Đạt được thứ tự công bằng tối ưu theo nghĩa giới hạn không công bằng hóa ra lại được kết nối với các thuộc tính lý thuyết biểu đồ của biểu đồ phụ thuộc giao dịch cơ bản, cụ thể là thước đo băng thông của các thành phần được kết nối mạnh trong biểu đồ này. Điều này dẫn đến một trường hợp cụ thể của định nghĩa mà các tác giả gọi là “thứ tự công bằng theo băng thông có hướng”, các tác giả cho thấy nó nắm bắt được điều tốt nhất có thể mà bất kỳ giao thức sổ cái nào cũng có thể đạt được về mặt giới hạn không công bằng. Các tác giả chứng minh thứ tự các giao dịch theo kiểu này là NP khó và không thể gần đúng với bất kỳ tỷ lệ không đổi nào. Để hiện thực hóa thuộc tính, các tác giả đưa ra một giao thức sổ cái phân tán mới có tên là Taxis nhằm đạt được thứ tự công bằng theo băng thông có hướng. Các tác giả trình bày hai biến thể, một biến thể hoàn toàn phù hợp với thuộc tính nhưng (nhất thiết) thiếu hiệu suất và tính linh động, biến thể còn lại đạt được tính linh động và độ phức tạp tốt hơn trong khi cung cấp một phiên bản hơi nới lỏng của thuộc tính. Cuối cùng, các tác giả nhận xét về các ứng dụng công việc của minhg vào sự lựa chọn xã hội, một hướng đi mà các tác giả tin là có lợi ích độc lập.
Đọc thêm các bài viết liên quan tại thẻ Tags bên dưới